#include "BTreeNode.h"

using namespace std;

BTLeafNode::BTLeafNode(){
	keyCount = 0;
	ridCount = 0;
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{ 
	BTLeafNode.pf = pf;
	//load the buffer
	RC rc = pf.read(pid, buffer);	
	if (rc < 0)
		return RC_FILE_READ_FAILED;
	//get the keyCount from first 4 characters
	memcpy(&keyCount, buffer, sizeof(int));
	ridCount = keyCount+1;

	//load the tables from the buffer
	char* cursor = buffer+sizeof(int);
	for (int i=0; i<ridCount; i++){
		memcpy(&ridArr[i], cursor, sizeof(RecordId));
		if (i<keyCount)
			memcpy(&keyArr[i], cursor+sizeof(RecordId), sizeof(int));	
		cursor += (sizeof(RecordId)+sizeof(int));
	}

	return 0;
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{ 
	//load the buffer
	char* cursor = buffer+sizeof(int);
	for (int i=0; i<ridCount; i++){
		memcpy(cursor, &ridArr[i], sizeof(RecordId));
		if (i<keyCount)
			memcpy(cursor+sizeof(RecordId),&keyArr[i], sizeof(int));	
		cursor += (sizeof(RecordId)+sizeof(int));
	}

	//write from buffer
	RC rc = pf.write(pid, buffer);	
	if (rc < 0)
		return RC_FILE_WRITE_FAILED;
	return 0;
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{ 
	int kC;
	memcpy(&kC, buffer, sizeof(int));
	return kC;  
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{ 
	int insAt = 0; //where to insert the key & rid

	if (keyCount == MAX_KEYS_PER_NODE)
		return RC_NODE_FULL;
	
	//find insertion point (index of first keyArr[i] > key)
	while (keyArr[insAt] <= key && insAt < keyCount)
		insAt++;

	//insert key
	for (int i = keyCount; i>insAt; i--)
		keyArr[i] = keyArr[i-1];

	keyArr[insAt] = key;
	keyCount++;
	
	//insert rid
	for (int j = ridCount; j>insAt; j--)
		ridArr[j] = ridArr[j-1];

	ridArr[insAt] = rid;
	ridCount++;


	return 0; 
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{ 
	int insAt = 0;
	//find insertion point (index of first keyArr[i] > key)
	while (keyArr[insAt] <= key && insAt < keyCount)
		insAt++;

	for (int i = keyCount/2; i < keyCount; i++)
	{
		sibling.insert(keyArr[i], ridArr[i]);
	}

	keyCount = keyCount/2;
	ridArr[keyCount] = ridArr[ridCount-1];
	ridCount = keyCount+1;

	if (insAt <= keyCount)
		insert(key, rid);
	else
		sibling.insert(key,rid);
	
	RecordId jj;
	sibling.readEntry(0, siblingKey, jj);

	return 0; 
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{ 
	int cursor = 0;
	//find insertion point (index of first keyArr[i] > key)
	while (keyArr[cursor] <= searchKey && cursor < keyCount)
		cursor++;
	if (cursor == keyCount)
		return RC_NO_SUCH_RECORD;

	return cursor; 
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{ 
	if (eid > keyCount)
		return RC_NO_SUCH_RECORD;
	key = keyArr[eid];
	rid = ridArr[eid];
	return 0; 
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{ 
	return ridArr[ridCount-1].pid; 
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{ 
	if (pid >= pf.endPid())
		return RC_INVALID_PID;

	ridArr[ridCount-1].pid = pid;
	return 0; 
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{ 
	BTNonLeafNode.pf = pf;
	//load the buffer
	RC rc = pf.read(pid, buffer);	
	if (rc < 0)
		return RC_FILE_READ_FAILED;

	//get the keyCount from first 4 characters
	memcpy(&keyCount, buffer, sizeof(int));
	pidCount = keyCount+1;

	//load the tables from the buffer
	char* cursor = buffer+sizeof(int);
	for (int i=0; i<pidCount; i++){
		memcpy(&pidArr[i], cursor, sizeof(PageId));
		if (i<keyCount)
			memcpy(&keyArr[i], cursor+sizeof(PageId), sizeof(int));	
		cursor += (sizeof(PageId)+sizeof(int));
	}

	return 0;
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{ 
	//load the buffer
	char* cursor = buffer+sizeof(int);
	for (int i=0; i<pidCount; i++){
		memcpy(cursor, &pidArr[i], sizeof(PageId));
		if (i<keyCount)
			memcpy(cursor+sizeof(PageId),&keyArr[i], sizeof(int));	
		cursor += (sizeof(PageId)+sizeof(int));
	}

	//write from buffer
	RC rc = pf.write(pid, buffer);	
	if (rc < 0)
		return RC_FILE_WRITE_FAILED;
	return 0; 
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{ 
	int kC;
	memcpy(&kC, buffer, sizeof(int));
	return kC; 
}


/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{ 
	int insAt = 0; //where to insert the key & rid

	if (keyCount == MAX_KEYS_PER_NODE)
		return RC_NODE_FULL;
	
	//find insertion point (index of first keyArr[i] > key)
	while (keyArr[insAt] <= key && insAt < keyCount)
		insAt++;

	//insert key
	for (int i = keyCount; i>insAt; i--)
		keyArr[i] = keyArr[i-1];

	keyArr[insAt] = key;
	keyCount++;
	
	//insert rid
	for (int j = pidCount; j>insAt; j--)
		pidArr[j] = pidArr[j-1];

	pidArr[insAt] = pid;
	pidCount++;

	return 0; 
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{ 
	int insAt = 0;
	//find insertion point (index of first keyArr[i] > key)
	while (keyArr[insAt] <= key && insAt < keyCount)
		insAt++;

	for (int i = keyCount/2; i < keyCount; i++)
	{
		sibling.insert(keyArr[i], pidArr[i]);
	}

	keyCount = keyCount/2;
	pidArr[keyCount] = pidArr[pidCount-1];
	pidCount = keyCount+1;

	if (insAt <= keyCount)
		insert(key, pid);
	else
		sibling.insert(key,pid);
	
	//push up the middle key
	midKey = keyArr[keyCount-1];
	keyCount--;
	pidCount--;

	return 0;  
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{ 
	int cursor = 0;
	while(searchKey > keyArr[cursor] && cursor < keyCount)
		cursor++;
	
	pid = pidArr[cursor];

	return 0; 
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{ 
	if (pid1 >= pf.endPid() || pid2 >= pf.endPid())
		return RC_INVALID_PID;
	pidArr[0] = pid1;
	pidArr[1] = pid2;
	keyArr[0] = key;
	return 0; 
}
